package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;
import com.algorithm.排序.tools.Integers;

public class 冒泡排序<E extends Comparable<E>> extends Sort<E> {

    //未优化的冒泡排序
    public static void bubbleSort(Integer[] array) {
        //第一层for循环：1.确定一共要比较多少轮（总共需要比较 array.length-1 次） 2.确定end的值，供第二层for循环使用
        for (int end = array.length - 1; end > 0; end--) {
            //第二层for循环：确定一轮比较多少次，就循环比较多少次
            for (int begin = 1; begin <= end; begin++) {
                //比较并交换
                if (array[begin - 1] > array[begin]) {
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;
                }
            }
        }
    }

    //优化后的冒泡排序 如果序列已经完全有序，可以提前终止冒泡排序
    public static void bubbleSort1(Integer[] array) {
        //第一层for循环：1.确定一共要比较多少轮（总共需要比较 array.length-1 次） 2.确定end的值，供第二层for循环使用
        for (int end = array.length - 1; end > 0; end--) {
            //使用一个sorted标记是否可以提前结束排序
            boolean sorted = true;
            //第二层for循环：确定一轮比较多少次，就循环比较多少次
            for (int begin = 1; begin <= end; begin++) {
                //比较并交换
                //如果某一轮的比较，发现没有进入到这个if里面去，说明数组已经有序，可以提前终止排序了
                if (array[begin - 1] > array[begin]) {
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }

    //优化后的冒泡排序 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
    @Override
    protected void sort() {
        //第一层for循环：1.确定一共要比较多少轮（总共需要比较 array.length-1 次） 2.确定end的值，供第二层for循环使用
        for (int end = array.length - 1; end > 0; end--) {
            //定义最后1次交换的位置
            //sortedIndex的初始值应该在数组完全有序的时候有用
            //当sortedIndex为1的时候end-- 减为0 跳出循环，写0,-1..均可
            int sortedIndex = 1;
            //第二层for循环：确定一轮比较多少次，就循环比较多少次
            for (int begin = 1; begin <= end; begin++) {
                //比较并交换
               /* if (array[begin - 1] > array[begin]) {
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;

                    //可以记录最后1次交换的位置，在这个位置之后都是排好序的不用再进行排序
                    sortedIndex = begin;
                }*/
                if (cmp(begin - 1, begin) > 0) {
                    swap(begin - 1, begin);

                    //可以记录最后1次交换的位置，在这个位置之后都是排好序的不用再进行排序
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

}